백준 12100번

오늘 풀어본 문제는 백준의 12100번 문제¹이다. 문제 풀이에 사용한 언어는 C++ 이다.

solved.ac 기준 CLASS

CLASS 5

문제 정보

이 문제의 내용과 조건은 다음과 같다.

문제

2048 게임은 $4 \times 4$ 크기의 보드에서 혼자 즐기는 재미있는 게임이다. 이 링크를 누르면 게임을 해볼 수 있다.

이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다)


<그림 1>	<그림 2>	<그림 3>

<그림 1>의 경우에서 위로 블록을 이동시키면 <그림 2>의 상태가 된다. 여기서, 왼쪽으로 블록을 이동시키면 <그림 3>의 상태가 된다.


<그림 4>	<그림 5>	<그림 6>	<그림 7>

<그림 4>의 상태에서 블록을 오른쪽으로 이동시키면 <그림 5>가 되고, 여기서 다시 위로 블록을 이동시키면 <그림 6>이 된다. 여기서 오른쪽으로 블록을 이동시켜 <그림 7>을 만들 수 있다.


<그림 8>	<그림 9>

<그림 8>의 상태에서 왼쪽으로 블록을 옮기면 어떻게 될까? 2가 충돌하기 때문에, 4로 합쳐지게 되고 <그림 9>의 상태가 된다.


<그림 10>	<그림 11>	<그림 12>	<그림 13>

<그림 10>에서 위로 블록을 이동시키면 <그림 11>의 상태가 된다.

<그림 12>의 경우에 위로 블록을 이동시키면 <그림 13>의 상태가 되는데, 그 이유는 한 번의 이동에서 이미 합쳐진 블록은 또 합쳐질 수 없기 때문이다.


<그림 14>	<그림 15>

마지막으로, 똑같은 수가 세 개가 있는 경우에는 이동하려고 하는 쪽의 칸이 먼저 합쳐진다. 예를 들어, 위로 이동시키는 경우에는 위쪽에 있는 블록이 먼저 합쳐지게 된다. <그림 14>의 경우에 위로 이동하면 <그림 15>를 만든다.

이 문제에서 다루는 2048 게임은 보드의 크기가 $N \times N$ 이다. 보드의 크기와 보드판의 블록 상태가 주어졌을 때, 최대 $5$ 번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 보드의 크기 $N$ $(1 \le N \le 20)$ 이 주어진다. 둘째 줄부터 $N$ 개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 $2$ 보다 크거나 같고, $1024$ 보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.

출력

최대 $5$ 번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.

풀이과정

1번째 시도

문제를 처음 보고 구현 및 시뮬레이션 문제라는 것을 알 수 있었다. 2048 게임을 시뮬레이션 해볼 수 있도록 Board 라는 클래스를 만들었고, 각 방향으로 미는 것을 swipeLeft 함수 하나를 이용하여 구현하였다.

swipeLeft 함수는 병합이 일어났는지 여부를 확인하고 새로운 행 벡터에 요소를 수정하거나 더한 뒤, 마지막에 행 벡터를 교체하는 방식으로 구현하였다.

얻어낼 수 있는 가장 큰 값을 알아내기 위해서, searchMax 함수를 재귀함수 형태로 만들었다.

코드는 다음과 같이 작성하였다.

#include <bits/stdc++.h>

using namespace std;

class Board {
private:
    int N;
    vector<vector<int>> grid;

    void flipHorizontal();
    void transpose();
public:
    Board();

    int searchMax(int depth);

    void swipeLeft();
    void swipeRight();
    void swipeUp();
    void swipeDown();

    int maxBlock();

    void printGrid();
};

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    Board board;

    cout << board.searchMax(5);

    return 0;
}

Board::Board() {
    cin >> N;
    grid.resize(N, vector<int>(N, 0));

    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            cin >> grid[i][j];
        }
    }
}

void Board::flipHorizontal() {
    for (int i=0; i<N; i++) {
        for (int j=0; j<(N/2); j++) {
            swap(grid[i][j], grid[i][N - 1 - j]);
        }
    }
}

void Board::transpose() {
    for (int i=0; i<(N-1); i++) {
        for (int j=i+1; j<N; j++) {
            swap(grid[i][j], grid[j][i]);
        }
    }
}

int Board::searchMax(int depth) {
    Board left = *this;
    Board right = *this;
    Board up = *this;
    Board down = *this;

    left.swipeLeft();
    right.swipeRight();
    up.swipeUp();
    down.swipeDown();

    if (depth > 1) {
        return max({left.searchMax(depth - 1), right.searchMax(depth - 1), up.searchMax(depth - 1), down.searchMax(depth - 1)});
    }
    else {
        return max({left.maxBlock(), right.maxBlock(), up.maxBlock(), down.maxBlock()});
    }
}

void Board::swipeLeft() {
    for (int i=0; i<N; i++) {
        vector<int> newRow;
        bool merged = false;

        for (int j=0; j<N; j++) {
            int curr = grid[i][j];
            if (curr == 0) {
                continue;
            }

            if (merged) {
                merged = false;
                newRow.emplace_back(curr);
            }
            else if (!newRow.empty() && newRow.back() == curr) {
                merged = true;
                newRow.back() += curr;
            }
            else {
                newRow.emplace_back(curr);
            }
        }

        int paddingCount = N - newRow.size();
        for (int j=0; j<paddingCount; j++) {
            newRow.emplace_back(0);
        }

        grid[i] = newRow;
    }
}

void Board::swipeRight() {
    flipHorizontal();
    swipeLeft();
    flipHorizontal();
}

void Board::swipeUp() {
    transpose();
    swipeLeft();
    transpose();
}

void Board::swipeDown() {
    transpose();
    swipeRight();
    transpose();
}

int Board::maxBlock() {
    int result = 0;

    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            result = max(result, grid[i][j]);
        }
    }

    return result;
}

void Board::printGrid() {
    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            cout << grid[i][j] << " ";
        }
        cout << "\n";
    }
}

그러자 모든 테스트 케이스를 통과하고 정답이 나오는 것을 확인할 수 있었다.

마무리

2048 게임은 학교에서 들었던 강의인 객체지향프로그래밍 마지막 과제에서 만들어 본 적이 있다. 간만에 보니 반가운 마음도 들었다. 이번에 짠 방식과는 조금 구현 방식이 다르긴 하지만, 그 강의 과제로 만든 2048 게임의 코드가 궁금하다면 내 깃헙 레포지토리²를 확인하면 된다.

오늘의 PS는 여기까지!

1: https://www.acmicpc.net/problem/12100
2: https://github.com/ChoiCube84/CSED232-Assignments/tree/main/Assignment5

← Previous Post Next Post →